Algorithms in Neuroscience

The goal of this lecture is to learn how to use computational principals to understand natural phenomena.

Biological systems, of all scales, have evolved to solve the challenges posed by their environments inorder to give themselves the best chance of survival and reproduction. Algorithms are processes or sets of rules used to solve classes of problems, which makes them a powerful tool to systemitize and describe these natural strategies.

Marr's Levels of Analysis

1. Computational: what does the system do, and why does it do these things

2. Algorithmic/representational level: how does the system do what it does

3. Implementational/physical level: how is the system physically realized

Reinforcement Learning

Reinforcement Learning (RL) is the process by which an agent learns to act in its environment such that it maximizes its cummulative reward.

Understanding RL is a fundamental challenge for neuroscience because it underpins how the brain learns to behave!

Challenges Facing RL

1. Curse of Dimensionality i.e. the world is way too complex brute force for trial and error

2. Temporal Credit Assignment

3. Imperfect Information

4. Exploration-Exploitation Dilemma

5. ...

Temporal Credit Assignment

Using Marr's framework what Computational problem must RL solve?

An agent must bind rewards to temporally distal prior states and actions.

We must introduce some symbols to describe this problem algebraically

Let $S_t$ be the state of the agent and environment at time $t$. Let $\pi$ be a policy, or a set of state-action pairs, $r_t$ be the reward at $S_t$, and $\lambda$ be the discount rate. $V^{\pi }\left(S_t\right)$ is the value of the state $S_t$ under the policy $\pi$.

$$V^{\pi }\left(S_t\right)=\sum _{t^{\prime }=0}^{\mathrm{\infty }}{\lambda }^{t^{\prime }}{r}_{t+t^{\prime }}$$

That is the value of the current state is the discounted sum of all the expected future rewards.

To derive an Algorithm to learn $V^{\pi }\left(S_t\right)$ we start by splitting the sum.

$$V^{\pi }\left(S_t\right)=r_t+\sum _{t^{\prime }=0}^{\mathrm{\infty }}{\lambda }^{(t+1)+t^{\prime }}{r}_{(t+1)+t^{\prime }}$$

We can now recursively define the function as

$$V^{\pi }\left(S_t\right)=r_t+V^{\pi }\left(S_{t+1}\right)$$

This recursive formulation gives us the simple learning rule

$$V^{\pi }\left(S_t\right)=V^{\pi }\left(S_t\right)+\alpha [r_t+\lambda V^{\pi }\left(S_{t+1}\right)\text{-}{V}^{\pi }\left(S_t\right)]$$

where $\alpha$ is the learning rate and $[r_t+\lambda V^{\pi }\left(S_{t+1}\right)\text{-}{V}^{\pi }\left(S_t\right)]$ is the reward prediction error.

This Temporal-Difference (TD) Learning!

TD Learning in the Brain

How might TD learning be implemented in the brain?

Dopaminergic activity in the SNc and VTA has been shown to indicate reward prediction error which could provide a substrate for neural TD learning.

Exploration-Exploitation Dilemma

To find the most optimal policy, agents must thoroughly search the space of possible states. However, practical contstraints require the agent to balance this exploration against prioritize known, high value states.

A common solution is to randomly sample states in porportion to their known value. One of the simplest sampling algorithms is called $\epsilon$-greedy. This algorithm samples the highest value state with probability $1\text{-}\epsilon$ and samples a random state with probability $\epsilon$.

TD Learning Example

Below is an implementation of TD learning to find the shortest path between two nodes on a graph. The Agent begins at the Start node, marked in red, and travels along the edges, from node to node, until it reaches the Terminal node, marked in blue, and recieves a reward. After each move the Agent updates its estimates for the value of each node which corresponds to how many moves it is away from the reward.

Graph Size:

16

Sparsity:

0.2

Start: End:

lamda:

0.76

alpha:

0.2

epsilon:

0.1

Run Sim: Iterations:

Defines Graph Maze

Defines Agent

Implements $\epsilon$-greedy algorithm

Implements TD Learning